public class Solution {
//    public String longestPalindrome(String s) {
//        int begin = 0, len = 0, n = s.length();
//        for(int i = 0; i < n; i++){
//            int left = i, right = i;
//            while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)){
//                left--;
//                right++;
//            }
//            if(right - left - 1 > len){
//                begin = left + 1;
//                len = right - left - 1;
//            }
//            left = i;
//            right = i + 1;
//            while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)){
//                left--;
//                right++;
//            }
//            if(right - left - 1 > len){
//                begin = left + 1;
//                len = right - left - 1;
//            }
//        }
//        return s.substring(begin,begin+len);
//    }

     public static String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];

        int begin = 0, len = 1;
        for(int i = n - 1; i >= 0; i--){
            for(int j = i; j < n; j++){
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = j - i > 1 ? dp[i + 1][j - 1] : true;
                }
                if(dp[i][j] && j - i + 1 > len){
                    begin = i;
                    len = j - i + 1;
                }
            }
        }
        return s.substring(begin, begin + len);
    }

    public boolean checkPartitioning(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];

        for(int i = n - 1; i >= 0; i--){
            for(int j = i; j < n; j++){
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = j - i > 1 ? dp[i + 1][j - 1] : true;
                }
            }
        }
        for(int i = 1; i < n - 1; i++){
            for(int j = i; j < n - 1; j++){
                if(dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1]){
                    return true;
                }
            }
        }
        return false;
    }

    public int minCut(String s) {
        int n = s.length();
        boolean[][] isPal = new boolean[n][n];

        for(int i = n - 1; i >= 0; i--){
            for(int j = i; j < n; j++){
                if(s.charAt(i) == s.charAt(j)){
                    isPal[i][j] = j - i > 1 ? isPal[i + 1][j - 1] : true;
                }
            }
        }

        int[] dp = new int[n];
        for(int i = 0; i < n; i++) { dp[i] = Integer.MAX_VALUE;}
        for(int i = 0; i < n; i++){
            if(isPal[0][i]){
                dp[i] = 0;
            }else{
                for(int j = 1; j <= i; j++){
                    if(isPal[j][i]){
                        dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                    }
                }
            }
        }
        return dp[n - 1];
    }

    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];

        for(int i = n - 1; i >= 0; i--){
            dp[i][i] = 1;
            for(int j = i + 1; j < n; j++){
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                }else{
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
                }
            }
        }
        return dp[0][n - 1];
    }

    public int minInsertions(String s) {
         int n = s.length();
         int[][] dp = new int[n][n];
         for(int i = n - 1; i >= 0; i--){
             for(int j = i + 1; j < n; j++){
                 if(s.charAt(i) == s.charAt(j)){
                     dp[i][j] = dp[i + 1][j - 1];
                 }else{
                     dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]);
                 }
             }
         }
         return dp[0][n - 1];
    }

    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(text1.charAt(i - 1) == text2.charAt(j -1)){
                    dp[i][j] = dp[i - 1][j -1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }

    public int longestCommonSubsequence2(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        text1 = " " + text1;
        text2 = " " + text2;
        int[][] dp = new int[m + 1][n + 1];

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(text1.charAt(i) == text2.charAt(j)){
                    dp[i][j] = dp[i - 1][j -1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }

    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[][] dp = new int[m + 1][n + 1];

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(nums1[i - 1] == nums2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }

    public int numDistinct(String s, String t) {
        int m = t.length(), n = s.length();
        int[][] dp = new int[m + 1][n + 1];
        for(int j = 0; j <= n; j++) { dp[0][j] = 1;}

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = dp[i][j - 1];
                if(t.charAt(i - 1) == s.charAt(j - 1)){
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }

    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        s = " " + s;
        p = " " + p;
        char[] elemS = s.toCharArray();
        char[] elemP = p.toCharArray();

        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for(int j = 1; j <= n; j++){
            if(elemP[j] == '*'){
                dp[0][j] = true;
            }else{
                break;
            }
        }

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(elemP[j] == '*'){
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                }else{
                    dp[i][j] = (elemP[j] == '?' || elemP[j] == elemS[i]) && dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }

//    public boolean isMatch(String s, String p) {
//        int m = s.length(), n = p.length();
//        s = " " + s;
//        p = " " + p;
//        char[] elemS = s.toCharArray();
//        char[] elemP = p.toCharArray();
//        boolean[][] dp = new boolean[m + 1][n + 1];
//
//        dp[0][0] = true;
//        for(int j = 2; j <= n; j += 2){
//            if(elemP[j] == '*'){
//                dp[0][j] = true;
//            }else{
//                break;
//            }
//        }
//
//        for(int i = 1; i <= m; i++){
//            for(int j = 1; j <= n; j++){
//                if(elemP[j] == '*'){
//                    dp[i][j] = dp[i][j - 2] || (elemP[j - 1] == '.' || elemP[j - 1] ==elemS[i]) && dp[i - 1][j];
//                }else{
//                    dp[i][j] = (elemP[j] == '.' || elemP[j] == elemS[i]) && dp[i - 1][j - 1];
//                }
//            }
//        }
//        return dp[m][n];
//    }

    public static boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length();
        if(m + n != s3.length()) { return false;}
        s1 = " " + s1;
        s2 = " " + s2;
        s3 = " " + s3;
        char[] elem1 = s1.toCharArray();
        char[] elem2 = s2.toCharArray();
        boolean[][] dp = new boolean[m + 1][n + 1];

        dp[0][0] = true;
        for(int i = 1; i <= m; i++){  //初始化第一列
            if(elem1[i] == s3.charAt(i)){
                dp[i][0] = true;
            }else{
                break;
            }
        }
        for(int j = 1; j <= n; j++){  //初始化第一行
            if(elem2[j] == s3.charAt(j)){
                dp[0][j] = true;
            }else{
                break;
            }
        }

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
//                if(elem1[i] == s3.charAt(i + j)){
//                    dp[i][j] = dp[i - 1][j];
//                }
//                if(elem2[j] == s3.charAt(i + j)){
//                    dp[i][j] = dp[i][j - 1];
//                }
                dp[i][j] = (elem1[i] == s3.charAt(i + j) && dp[i - 1][j])
                        || (elem2[j] == s3.charAt(i + j) && dp[i][j - 1]);
            }
        }
        return dp[m][n];
    }

    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                if(s1.charAt(i - 1) == s2.charAt(j - 1)){
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + s1.charAt(i - 1));
                }
            }
        }

        int sum = 0;
        for(char ch : s1.toCharArray()) { sum += ch;}
        for(char ch : s2.toCharArray()) { sum += ch;}
        return sum - dp[m][n] - dp[m][n];
    }

    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[][] dp = new int[m + 1][n + 1];

        int ret = 0;
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(nums1[i - 1] == nums2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] = 0;
                }
                ret = Math.max(ret, dp[i][j]);
            }
        }
        return ret;
    }

    public static void main(String[] args) {
//         String s1 = "babad";
//        System.out.println(longestPalindrome(s1));

        String s1 = "ab", s2 = "bc", s3 ="babc";
        System.out.println(isInterleave(s1,s2,s3));
    }


}